package com.cat.chapter048;

/**
 * @author cat
 * @description https://leetcode.cn/problems/range-sum-query-2d-immutable/
 * @create 2025/7/16 16:23
 * @since JDK17
 */

public class NumMatrix {
    static int n, m;
    static int[][] arr;

    public NumMatrix(int[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;
        arr = new int[n + 1][m + 1];
        // 将前缀和数组处理好
        for (int a = 0, b = 1; b <= n; a++, b++) {
            for (int c = 0, d = 1; d <= m; c++, d++) {
                arr[b][d] = matrix[a][c];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int a, int b, int c, int d) {
        return arr[c + 1][d + 1] - arr[a][d + 1] - arr[c + 1][b] + arr[a][b];
    }
}
